//请判断一个链表是否为回文链表。 
//
// 示例 1: 
//
// 输入: 1->2
//输出: false 
//
// 示例 2: 
//
// 输入: 1->2->2->1
//输出: true
// 
//
// 进阶： 
//你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？ 
// Related Topics 链表 双指针 
// 👍 624 👎 0

package leetcode.editor.cn;

//Java：回文链表
public class P234PalindromeLinkedList {

    /*
     * 思路：    1.快慢指针找出 中位数  1 2 3 4 [5] 4 3 2 1
     *          2.后半段翻转  [1] 2 3 4 5 [1] 2 3 4
     *          3.从头和从中点遍历，相等的就是回文，不等的就是非回文
     *
     * 执行用时： 1 ms , 在所有 Java 提交中击败了 99.76% 的用户 内存消耗： 42.5 MB , 在所有 Java 提交中击败了 52.92% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode(int x) { val = x; }
     * }
     */
    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    class Solution {
        public boolean isPalindrome(ListNode head) {
            if (head == null) {
                return true;
            }
            ListNode slow = head;
            ListNode fast = head.next;

            // 快慢指针 寻找中点 slow
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }


            // 中点后半部分反转
            // 1 2 3 4 [5] 4 3 2 1
            // 1 2 3 4 [5] 3 4 2 1
            // 大于两个结点才翻转
            if (slow.next != null) {
                ListNode now = slow.next.next;  //3
                ListNode last = slow.next;    // 4
                ListNode first = slow.next;    // 4
                while (now != null) {
                    last.next = now.next;
                    now.next = first;
                    first = now;
                    slow.next = first;
                    now = last.next;
                }
            }


            slow = slow.next;
            while (slow != null) {
                if (head.val != slow.val) {
                    return false;
                }
                head = head.next;
                slow = slow.next;
            }
            return true;

        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P234PalindromeLinkedList().new Solution();
        ListNode node = new ListNode(1);
        System.out.println(solution.isPalindrome(node));
        // TO TEST
    }

    private static ListNode add(ListNode listNode, int x) {
        ListNode node = new ListNode(x);
        node.next = listNode;
        return node;
    }

}